{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_rods(move, towers, left, middle, right):\n",
    "    if towers:\n",
    "        if (move << 1) & (1 << towers):\n",
    "            right.append(towers)\n",
    "            get_rods(move, towers - 1, middle, left, right)\n",
    "        else:\n",
    "            left.append(towers)\n",
    "            get_rods(move, towers - 1, left, right, middle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_move(towers, left, middle, right):\n",
    "    if not towers:\n",
    "        return 0\n",
    "    if not left or right and left[0] < right[0]:\n",
    "        move = 1 << (towers - 1)\n",
    "        return move + get_move(towers - 1, middle, left, right[1:])\n",
    "    else:\n",
    "        return get_move(towers - 1, left[1:], right, middle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hanoi(towers):\n",
    "    for i in range(2 ** towers):\n",
    "        rods = [], [], []\n",
    "        get_rods(i, towers, *rods)\n",
    "        move = get_move(towers, *rods)\n",
    "        print('{:2} moves -- {} {} {}'.format(move, *rods))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 moves -- [2, 1] [] []\n",
      " 1 moves -- [2] [1] []\n",
      " 2 moves -- [] [1] [2]\n",
      " 3 moves -- [] [] [2, 1]\n"
     ]
    }
   ],
   "source": [
    "hanoi(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 moves -- [3, 2, 1] [] []\n",
      " 1 moves -- [3, 2] [] [1]\n",
      " 2 moves -- [3] [2] [1]\n",
      " 3 moves -- [3] [2, 1] []\n",
      " 4 moves -- [] [2, 1] [3]\n",
      " 5 moves -- [1] [2] [3]\n",
      " 6 moves -- [1] [] [3, 2]\n",
      " 7 moves -- [] [] [3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "hanoi(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 moves -- [4, 3, 2, 1] [] []\n",
      " 1 moves -- [4, 3, 2] [1] []\n",
      " 2 moves -- [4, 3] [1] [2]\n",
      " 3 moves -- [4, 3] [] [2, 1]\n",
      " 4 moves -- [4] [3] [2, 1]\n",
      " 5 moves -- [4, 1] [3] [2]\n",
      " 6 moves -- [4, 1] [3, 2] []\n",
      " 7 moves -- [4] [3, 2, 1] []\n",
      " 8 moves -- [] [3, 2, 1] [4]\n",
      " 9 moves -- [] [3, 2] [4, 1]\n",
      "10 moves -- [2] [3] [4, 1]\n",
      "11 moves -- [2, 1] [3] [4]\n",
      "12 moves -- [2, 1] [] [4, 3]\n",
      "13 moves -- [2] [1] [4, 3]\n",
      "14 moves -- [] [1] [4, 3, 2]\n",
      "15 moves -- [] [] [4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "hanoi(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 moves -- [5, 4, 3, 2, 1] [] []\n",
      " 1 moves -- [5, 4, 3, 2] [] [1]\n",
      " 2 moves -- [5, 4, 3] [2] [1]\n",
      " 3 moves -- [5, 4, 3] [2, 1] []\n",
      " 4 moves -- [5, 4] [2, 1] [3]\n",
      " 5 moves -- [5, 4, 1] [2] [3]\n",
      " 6 moves -- [5, 4, 1] [] [3, 2]\n",
      " 7 moves -- [5, 4] [] [3, 2, 1]\n",
      " 8 moves -- [5] [4] [3, 2, 1]\n",
      " 9 moves -- [5] [4, 1] [3, 2]\n",
      "10 moves -- [5, 2] [4, 1] [3]\n",
      "11 moves -- [5, 2, 1] [4] [3]\n",
      "12 moves -- [5, 2, 1] [4, 3] []\n",
      "13 moves -- [5, 2] [4, 3] [1]\n",
      "14 moves -- [5] [4, 3, 2] [1]\n",
      "15 moves -- [5] [4, 3, 2, 1] []\n",
      "16 moves -- [] [4, 3, 2, 1] [5]\n",
      "17 moves -- [1] [4, 3, 2] [5]\n",
      "18 moves -- [1] [4, 3] [5, 2]\n",
      "19 moves -- [] [4, 3] [5, 2, 1]\n",
      "20 moves -- [3] [4] [5, 2, 1]\n",
      "21 moves -- [3] [4, 1] [5, 2]\n",
      "22 moves -- [3, 2] [4, 1] [5]\n",
      "23 moves -- [3, 2, 1] [4] [5]\n",
      "24 moves -- [3, 2, 1] [] [5, 4]\n",
      "25 moves -- [3, 2] [] [5, 4, 1]\n",
      "26 moves -- [3] [2] [5, 4, 1]\n",
      "27 moves -- [3] [2, 1] [5, 4]\n",
      "28 moves -- [] [2, 1] [5, 4, 3]\n",
      "29 moves -- [1] [2] [5, 4, 3]\n",
      "30 moves -- [1] [] [5, 4, 3, 2]\n",
      "31 moves -- [] [] [5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "hanoi(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
